#include<iostream>
#include<string>
#include <string>
#include <stack>
#include <map>
using namespace std;



bool solve(string s){
   //i,j,k A B C   0: ( 1: )
    stack<char> st;
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                while(!st.empty()){
                    st.pop();
                }
                for(int x=0;x<s.length();x++){
                    if(s[x]=='A'&& i==0){
                        if(st.empty() || !st.empty()&&st.top()=='('){
                            st.push('(');
                        }
                    }else if(s[x]=='A'&& i==1){
                        if(st.empty()||!st.empty()&&st.top()==')'){
                            st.push(')');
                        }else if(st.top()=='('){
                            st.pop();
                        }else{
                            st.push(')');
                        }
                        
                    }
                    if(s[x]=='B'&& j==0){
                        if(st.empty() || !st.empty()&&st.top()=='('){
                            st.push('(');
                        }
                    }else if(s[x]=='B'&& j==1){
                        if(st.empty()||!st.empty()&&st.top()==')'){
                            st.push(')');
                        }else if(st.top()=='('){
                            st.pop();
                        }else{
                            st.push(')');
                        }
                        
                    }
                    
                    if(s[x]=='C'&& k==0){
                        if(st.empty() || !st.empty()&&st.top()=='('){
                            st.push('(');
                        }
                    }else if(s[x]=='C'&& k==1){
                        if(st.empty()||!st.empty()&&st.top()==')'){
                            st.push(')');
                        }else if(st.top()=='('){
                            st.pop();
                        }else{
                            st.push(')');
                        }
                        
                    }
                    
                }
                if(st.empty()){
                    // cout << i << " "<< j << " " << k <<endl;
                    return true;
                }
            }
        }
    }
    return false;
}   


int main(){
   freopen("in.txt","r",stdin);
    int n;
    cin >> n;
    string s;
    while(n--){
        cin >> s;
        if(solve(s)){
            cout << "YES"<<endl;
        }else{
            cout << "NO"<<endl;
        }
    }


    return 0;
}